/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        496.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/18 11:04
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给你两个 没有重复元素 的数组nums1 和nums2，其中nums1是nums2的子集。
//
//请你找出 nums1中每个元素在nums2中的下一个比其大的值。
//
//nums1中数字x的下一个更大元素是指x在nums2中对应位置的右边的第一个比x大的元素。如果不存在，对应位置输出 -1 。
#include "../header.h"

class Solution {
public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
        vector<int> ans(nums1.size());
        stack<int> stack;
        unordered_map<int, int> map;
        for (int i = 0; i < nums2.size(); ++i) {
            while (!stack.empty() && stack.top() < nums2[i]) {
                map[stack.top()] = nums2[i];
                stack.pop();
            }
            stack.push(nums2[i]);
        }
        while (!stack.empty()) {
            map[stack.top()] = -1;
            stack.pop();
        }
        for (int i = 0; i < nums1.size(); ++i) {
            ans[i] = map[nums1[i]];
        }
        return ans;
    }
};

